package com.leetcode.design;

import java.util.*;

/**
 * @author Dennis Li
 * @date 2020/10/13 14:40
 */
public class LFUCache {

    static class Node {
        int key, value, times = 1;

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    private int capacity;

    private Map<Integer, Node> map;
    // 采用TreeMap，对key进行排序，第一个key就是最小的次数
    private TreeMap<Integer, LinkedHashSet<Node>> minNodes;

    public LFUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        minNodes = new TreeMap<>();
    }

    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        Node node = map.get(key);
        node.times++;
        updateMinNodes(node);
        return node.value;
    }

    public void put(int key, int value) {
        // 容量为0，所有put直接返回
        if (capacity == 0) return;
        Node node;
        if (map.containsKey(key)) {
            node = map.get(key);
            node.value = value;
            node.times++;
        } else {
            if (map.size() == capacity) {
                deleteMinNode();
            }
            node = new Node(key, value);
            map.put(key, node);
        }
        updateMinNodes(node);
    }

    private void deleteMinNode() {
        // TreeMap的特性。会按照key进行排序
        LinkedHashSet<Node> nodes = minNodes.firstEntry().getValue();
        Node node = nodes.iterator().next();
        map.remove(node.key);
        if (nodes.size() == 1) {
            minNodes.remove(node.times);
        } else {
            nodes.remove(node);
        }
    }

    private void updateMinNodes(Node node) {
        int times = node.times;
        if (!minNodes.containsKey(times)) {
            minNodes.put(times, new LinkedHashSet<>());
        }
        // 在新的次数里面添加
        minNodes.get(times).add(node);
        // 如果已经出现过，那么将原本的次数更新
        if (minNodes.containsKey(times - 1)) {
            LinkedHashSet<Node> set = minNodes.get(times - 1);
            if (set.size() == 1) {
                // 只有一个，直接删除键
                minNodes.remove(times - 1);
            } else {
                set.remove(node);
            }
        }
    }
}
